package lbj.cyw.dp;
/*
* 5.
*   最长回文子串动态规划解法
*   也可用中心扩散法,中心扩散要考虑奇偶，i与i+1
* */
public class LongestPalindrome5 {
    public String longestPalindrome(String s){
        if(s.length()<2){
            return s;
        }
        int n=s.length();
        boolean[][] dp=new boolean[n][n];
        char[] chars = s.toCharArray();
        for (int i = 0; i < n; i++) {
            dp[i][i]=true;
        }
        int max=1;
        int begin=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(chars[i]!=chars[j]){
                    dp[i][j]=false;
                }else {
                    if ((j-i)<3){
                        dp[i][j]=true;
                    }else {
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && (j-i+1)>max){
                    max=(j-i+1);
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+max);
    }
}
